package io.github.handyang.algorithms.sort;

import lombok.extern.slf4j.Slf4j;

import java.util.AbstractMap;
import java.util.LinkedList;
import java.util.Map;

@Slf4j
public class IterationQuickSortAlgorithms implements SortAlgorithms {

    @Override
    public void sort(int[] arr) {
        LinkedList<Map.Entry<Integer, Integer>> queue = new LinkedList<>();

        queue.push(new AbstractMap.SimpleEntry<>(0, arr.length - 1));

        while (!queue.isEmpty()) {
            Map.Entry<Integer, Integer> pop = queue.pop();
            int start = pop.getKey();
            int end = pop.getValue();

            if (start >= end) continue;
            int newIndex = sort(arr, start, end);
            queue.push(new AbstractMap.SimpleEntry<>(start, newIndex - 1));
            queue.push(new AbstractMap.SimpleEntry<>(newIndex + 1, end));
        }
    }

    private int sort(int[] arr, int start, int end) {
//        log.info("start:{}, end:{}", start, end);
        int key = arr[start];

        int i = start, j = end;
        while (i < j) {
            while (i < j && arr[j] > key) j--;
            if (i < j) {
                arr[i++] = arr[j];
            }

            while (i < j && arr[i] < key) i++;
            if (i < j) {
                arr[j--] = arr[i];
            }
        }

        arr[i] = key;
        return i;
    }
}
